import utils.TreeNode;

/**
 * @Author ZhangCuirong
 * @Date 2025/10/10 16:04
 * @description:
 */
public class Solution222 {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = 0;
        int rightHeight = 0;
        TreeNode leftNode = root;
        TreeNode rightNode = root;
        while (leftNode != null) {
            leftNode = leftNode.left;
            leftHeight++;
        }
        while (rightNode != null) {
            rightNode = rightNode.right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (int) (Math.pow(2, leftHeight) - 1);
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
}
